Who Else Wants to understand the Kruskal Algorithm ?

Articles Details
Type: Computer Science Theory
Subject: Linear Programming
Background: Algorithm, Graph.

Kruskal algorithm is a method that helps to find a Minimum Spanning Tree from a connected weighted graph. In this article we will learn the essential of the kruskal algorithm beginning with the Linear problem behind it and finishing with it computational complexity.

Introduction

Kruskal Algorithm is a solution to the Shortest Spanning Tree Problem. Let’s begin with some definitions:

• A Tree is a connected graph with no cycle.
• the Spanning tree included in a graph is a Tree who touches all the nodes of this graph.
• A Weighted Graph is a graph where every edge has a cost named Weight which usually have a logical meaning.

What does the Shortest Spanning Tree Problem is all about ?

We have a connected weighted graph and we search for Spanning tree with the minimum cost. Now we will see the approach of the Kruskal Algorithm to resolve this problem.

Intuitive Idea

As we all know an algorithm always have an intuitive idea to follow. The Kruskal algorithm use a contructive approach, he construct the tree one arc(edge) at the time. Let’s move to the structure of the algorithm.

Algorithm Structure

1. create a forest F (a set of trees), where each node in the graph is a separate tree
2. create a set S containing all the edges in the graph
3. while S is non empty and F is not yet spanning
   1. remove an edge with minimum weight from S
   2. if that edge connects two different trees, then add it to the forest, combining two trees into a single tree
   3. otherwise discard that edge

At the termination of the algorithm, the forest has only one component and forms a minimum spanning tree of the graph.
Now we will see the computational complexity of this algorithm.

Algorithm Complexity

We are looking for the execution time in respect with the input size of our problem. Let’s assume we have a graph of n nodes and m edges.
Let’s consider in more detail the Step 3:
3.1 means to order all arcs in ascending order of their weight. So S contains at max m edges, so with a Quicksort, the execution time of this step is O(logm).
Steps 3.2 and 3.3 can be execute in constant time (it’s a decision).
Now we do the step 3 m times (number of edges)
So the complexity is O(mlogm).

Conclusion

In this article, we’ve covered the Intuitive idea behind the Kruskal algorithm and his computation complexity. Now if want to see the algorithm in action, you can find some Java applet. I advise to visit this one:

5 Java applets demos for the Kruskal algorithm

Thank you for your time!